package someTestExcemple.huaweiOd.greedyMethod;

//华为OD机试 - 阿里巴巴找黄金宝箱(II) - 贪心思维（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/131944878
//思路
/*先按出现个数降序排序；
        然后从降序数组中取数字，和原数组大小的一半（奇数的话向上取整）进行比较，大于等于即可；
        输出一共取了几次。*/
import java.util.*;
public class GoldChestII {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[]arr = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        System.out.println(Arrays.toString(arr));
        //按出现频率排序 数字几-出现次数
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<arr.length;i++) {
            int num = map.getOrDefault(arr[i],0);
            //map.put(i,num++); //先用num，再让num+1，这样实际存值没有加上1
            num++;
            map.put(arr[i],num);
        }
        sc.close();
        //按数字出现次数降序 是b-a别写反了
        //由于map是无序的，所以要再封装成List排序
        List<Map.Entry<Integer,Integer>> entryList = new ArrayList<>(map.entrySet());
        entryList.sort((a,b)-> b.getValue()-a.getValue());
        System.out.println(Arrays.toString(entryList.stream().toArray()));
        int sum =0;
        int step =0;
        for(int i=0;i<entryList.size();i++) {
            sum+= entryList.get(i).getValue();
            step++;
            if(sum>= arr.length/2) {
                break;
            }

        }
        System.out.println(step);


    }
}
